1290C - Prefix Enlightenment - CodeForces Solution

#ifndef DEBUG
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,abm,mmx,fma,popcnt")
#endif

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int INF = 1e18;

// #ifdef DEBUG
// template <typename T>
// struct myvector : public vector<T> {
//     using vector<T>::vector;
//     const T& operator[](size_t index) const {
//         return this->at(index);
//     }
//     T& operator[](size_t index) {
//         return this->at(index);
//     }
// };
// #define vector myvector
// #endif

vector<int> boss;
vector<pair<int, int>> val;
vector<bool> use;
vector<int> prev_cost;
int find(int a) {
    if (boss[a] == a) return a;
    return boss[a] = find(boss[a]);
}

void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return;
    boss[b] = a;
    val[a].first += val[b].first;
    val[a].second += val[b].second;
    val[a].first = min(INF, val[a].first);
    val[a].second = min(INF, val[a].second);
    use[a] = use[a] | use[b];
    prev_cost[a] += prev_cost[b];
}

bool comp(int a, int b) {
    if (a==INF) return false;
    if (b==INF) return true;
    if (a==0) return false;
    if (b==0) return true;
    return a<b;
}

void solve() {
    int n, k; 
    cin >> n >> k;

    string s; cin >> s;

    // if (n > 10000) 
    //     cout << s << "\n";

    // vector<vector<int>>()
    vector<vector<int>> contains(n);
    vector<vector<int>> subsets;
    for (int i=0; i<k; i++) {
        subsets.push_back({});
        int c; cin >> c;
        for (int j=0; j<c; j++) {
            int x; cin >> x;
            x--;
            contains[x].push_back(i);
            subsets[i].push_back(x);
        }
        sort(subsets[i].begin(), subsets[i].end());
    }
    sort(subsets.begin(), subsets.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    });

    boss.assign(2*k, 0);
    val.assign(2*k, {0, 0});
    use.assign(2*k, 0);
    for (int i=0; i<k; i++) {
        val[i].first=1;
    }
    for (int i=k; i<2*k; i++) {
        val[i].second=1;
    }
    iota(boss.begin(), boss.end(), 0LL);

    prev_cost.assign(2*k, 0LL);
    // vector<bool> seen(n, 0);
    int res = 0;
    for (int i=0; i<n; i++) {
        if (contains[i].size() == 2) {
            int a = contains[i][0];
            int b = contains[i][1];

            res -= prev_cost[find(a)];
            res -= prev_cost[find(a+k)];
            // res -= max((int)seen[a], min({val[find(a)].first, val[find(a)].second}));
            if (find(a) != find(b) && find(a) != find(b+k)) {
                res -= prev_cost[find(b)];
                res -= prev_cost[find(b+k)];
                // res -= max((int)seen[b], min({val[find(b)].first, val[find(b)].second}));
            }
            if (s[i] == '0') {
                unite(a, b+k);
                unite(a+k, b);
            } else {
                unite(a, b);
                unite(a+k, b+k);
            }

            if (s[i] == '0') {
                use[find(a)] = true;
                use[find(a+k)] = true;
            }

            // res += max(1LL, min({val[find(a)].first, val[find(a)].second}));
            prev_cost[find(a)] = max((int)use[find(a)], min({val[find(a)].first, val[find(a)].second, val[find(a+k)].first, val[find(a+k)].second}, comp));
            prev_cost[find(a+k)] = max((int)use[find(a+k)], min({val[find(a)].first, val[find(a)].second, val[find(a+k)].first, val[find(a+k)].second}, comp));
            if (!use[find(a)]) prev_cost[find(a)]=0;
            if (!use[find(a+k)]) prev_cost[find(a+k)]=0;
            // if (val[find(a)].first>=INF && val[find(a)].second>=INF) prev_cost[find(a)] = 0;
            // if (val[find(a)].first>=INF && val[find(a)].second==0) prev_cost[find(a)] = 0;
            // if (val[find(a)].first==0 && val[find(a)].second>=INF) prev_cost[find(a)] = 0;
            // if (val[find(a+k)].first>=INF && val[find(a+k)].second>=INF) prev_cost[find(a+k)] = 0;
            // if (val[find(a+k)].first>=INF && val[find(a+k)].second==0) prev_cost[find(a+k)] = 0;
            // if (val[find(a+k)].first==0 && val[find(a+k)].second>=INF) prev_cost[find(a+k)] = 0;
            res += prev_cost[find(a)];
            res += prev_cost[find(a+k)];
            // if ((s[i] == '0' && find(a) != find(b)) || (s[i] == '1' && s[i] == '0')) {
            //     // res += max(1LL, min({val[find(b)].first, val[find(b)].second}));
            //     prev_cost[find(b)] = max(1LL, min({val[find(b)].first, val[find(b)].second, val[find(b+k)].first, val[find(b+k)].second}, comp));
            //     res += prev_cost[find(b)];
            // }
            
            // seen[a] = true;
            // seen[b] = true;
        } else if (contains[i].size() == 1) {
            int a = contains[i][0];
            // res -= max((int)seen[a], min({val[find(a)].first, val[find(a)].second}));
            res -= prev_cost[find(a)];
            res -= prev_cost[find(a+k)];
            if (s[i] == '1') {
                val[find(a)].first = INF;
                val[find(a+k)].second = INF;
            } else {
                val[find(a)].second = INF;
                val[find(a+k)].first = INF;
            }
            
            if (s[i] == '0') {
                use[find(a)] = true;
                use[find(a+k)] = true;
            }

            // res += max(1LL, min({val[find(a)].first, val[find(a)].second}));
            // seen[a] = true;
            prev_cost[find(a)] = max((int)use[find(a)], min({val[find(a)].first, val[find(a)].second, val[find(a+k)].first, val[find(a+k)].second}, comp));
            prev_cost[find(a+k)] = max((int)use[find(a+k)], min({val[find(a)].first, val[find(a)].second, val[find(a+k)].first, val[find(a+k)].second}, comp));
            if (!use[find(a)]) prev_cost[find(a)]=0;
            if (!use[find(a+k)]) prev_cost[find(a+k)]=0;
            // if (val[find(a)].first>=INF && val[find(a)].second>=INF) prev_cost[find(a)] = 0;
            // if (val[find(a)].first>=INF && val[find(a)].second==0) prev_cost[find(a)] = 0;
            // if (val[find(a)].first==0 && val[find(a)].second>=INF) prev_cost[find(a)] = 0;
            // if (val[find(a+k)].first>=INF && val[find(a+k)].second>=INF) prev_cost[find(a+k)] = 0;
            // if (val[find(a+k)].first>=INF && val[find(a+k)].second==0) prev_cost[find(a+k)] = 0;
            // if (val[find(a+k)].first==0 && val[find(a+k)].second>=INF) prev_cost[find(a+k)] = 0;
            res += prev_cost[find(a)];
            res += prev_cost[find(a+k)];
        }
        cout << res/2 << "\n";
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    try {
        solve();
    } catch (const out_of_range& e) {
        cerr << "ERROR!" << "\n";
        while (true) {};
    }
}